\documentclass[submission]{FPSAC2017}

\articlenumber{18}
\addbibresource{18_Gay_Hivert.bib}

\usepackage[utf8]{inputenc}
\usepackage{lipsum}
\usepackage{genyoungtabtikz}
\usepackage{mathtools}
\usepackage{stmaryrd}

\newtheorem{theorem}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{example}{Example}
\newtheorem{fact}{Fact}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
\newtheorem{notation}{Notation}
\newtheorem{note}{Note}


\newcommand\ylw{\Yfillcolour{yellow}}
\newcommand\whi{\Yfillcolour{white}}
\newcommand\red{\Yfillcolour{red}}
\newcommand\blu{\Yfillcolour{blue}}
\newcommand\lime{\Yfillcolour{lime}}


\newcommand{\RR}{\mathcal{R}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\JJ}{\mathcal{J}}
\newcommand{\KK}{\mathcal{K}}
\newcommand{\suchthat}{\mid}
\newcommand{\K}{\mathbb{K}}

\newcommand{\tMonoid}{M}
\newcommand{\lfix}[1]{\operatorname{lfix}(#1)}
\newcommand{\rfix}[1]{\operatorname{rfix}(#1)}
\newcommand{\idempMon}[1][\tMonoid]{E(#1)} % idempotent of a monoid

\DeclareMathOperator{\Id}{\mathbb{Id}}
\DeclareMathOperator{\NN}{\mathbb{N}}
\DeclareMathOperator{\ZZ}{\mathbb{Z}}
\DeclareMathOperator{\Inv}{Inv} % ensemble d'inversions
\DeclareMathOperator{\supp}{Supp} % support
\DeclareMathOperator{\cont}{Cont} % support
\DeclareMathOperator{\rad}{Rad} % radical
\newcommand{\col}[2]{\scalebox{0.6}{\begin{tabular}{ | c | }
     \hline
     $#1$ \\ 
     {\vdots} \\ 
     $#2$ \\ 
     \hline
   \end{tabular}} }
\DeclareMathOperator{\res}{Res}
\DeclareMathOperator{\ind}{Ind}


\title{The $0$-rook Monoid and its Representation Theory}

\author{Jo\"el Gay \and Florent Hivert}

\address{Laboratoire de Recherche en Informatique (UMR CNRS
  8623),
  Univ. Paris-Sud,
  Univ. Paris-Saclay,
  B\^at 650 Ada Lovelace, Rue Noetzlin, 91190 Gif-sur-Yvette\\}

\received{November 14, 2016}

\abstract{We show that a proper degeneracy at $q=0$ of the $q$-deformed rook
  monoid of Solomon is the algebra of a monoid $R_n^0$ namely the $0$-rook
  monoid, in the same vein as Norton's $0$-Hecke algebra being the algebra of
  a monoid $H_n^0 := H_n^0(A)$ (in Cartan type~A).  As expected, $R_n^0$ is
  closely related to the latter: it contains the $H_n^0(A)$ monoid and is a
  quotient of $H_n^0(B)$. It shares many properties with $H_n^0$, in
  particular it is $\JJ$-trivial. It allows us to describe its representation
  theory including the description of the simple and projective modules. We
  further show that $R_n^0$ is projective on $H_n^0$ and make explicit the
  restriction and induction along the inclusion map. A more surprising fact is
  that there are several non classical tower structures on the family of
  $(R_n^0)_{n\in \NN}$ and we discuss some work in progress on their
  representation theory.}

\keywords{combinatorics, representation theory of monoids, symmetric group,
  Iwahori-Hecke algebras, rook monoid}

\newcommand{\TODO}[1]{\marginpar{\small To do: #1} }
\newcommand{\Change}[1]{\marginpar{\small Change: #1} }


\begin{document}

\maketitle

\section*{Introduction}\label{intro}
The Iwahori-Hecke algebra were defined by Iwahori in \cite{Iw} in the
following way: let $q$ be a prime power and let $M =
\mathbf{M}_n(\mathbb{F}_q)$ be the monoid of all $n\times n$ matrices over
$\mathbb{F}_q$. Let $G = \mathbf{GL}_n(\mathbb{F}_q) \subset M$ be the general
linear group, and let $B\subset G$ be the Borel subgroup of upper triangular
matrices. The Bruhat decomposition can be written $G = \coprod_{\sigma \in
  \mathfrak{S}_n} B\sigma B$ where $\mathfrak{S}_n$ is the symmetric
group. For $\sigma\in \mathfrak{S}_n$ let $T_\sigma = \frac{1}{\vert B\vert}\sum_{x\in
  B\sigma B} x \in \mathbb{C}G$. The Hecke ring is the $\mathbb{Z}$-ring spanned by
the $T_\sigma$ and denoted by $\mathcal{H}_\mathbb{C}(G,B)$. Iwahori then proved
that this definition can be extended for $q$ outside of prime powers and this
Hecke algebra, denoted by $\mathcal{H}_n(q)$, has a presentation given by
generators $T_1, \dots, T_{n-1}$ (where $T_i := T_{s_i}$) and relations
$$\begin{array}{lll}
(1) & T_i^2 = q\cdot 1 + (q-1)T_i, & 1\leq i \leq n-1, \\
(2) & T_iT_{i+1}T_i = T_{i+1}T_iT_{i+1} & 1\leq i \leq n-2, \\
(3) & T_iT_j = T_jT_i & \text{if } \vert i-j\vert \geq 2. 
\end{array}$$


L. Solomon \cite{So1} studied the Iwahori algebra $\mathcal{H}_\mathbb{C}(M,
B)$. The Bruhat decomposition is now $M = \coprod_{r\in R_n} BrB$ where $R_n$
is the set of \emph{rook matrices} consisting of $n\times n$ matrices with entries
$\lbrace 0,1\rbrace$ and at most one nonzero entry in each row and column; see
\cite{Re}. Those matrices form a monoid (a generalization of groups in which
the elements do not have to be invertible), called the rook monoid. In
\cite{So2}, Solomon described a generalization $\mathcal{I}_n(q)$ outside of
prime powers and a first presentation, which Halverson reformulated in
\cite{Ha} into the following one, with generators $T_1, \dots, T_{n-1}, P_1,
\dots, P_n$ together with Relations~(1) (2) and (3) above and extra relations:
$$
\begin{array}{lll}\label{presqrook}
(4) & P_i^2 = P_i, &  1\leq i \leq n,\\
(5) & P_i P_j = P_j P_i, & 1\leq i,j \leq n,\\
(6) & P_i T_j = T_j P_i, & 1\leq i<j \leq n, \\
(7) & P_i T_j = T_j P_i = q P_i & 1\leq j<i \leq n,\\
(8) & P_{i+1} = q P_i T_i^{-1} P_i & 1\leq i < n.
\end{array}$$


The $0$-Hecke algebra is the degeneracy at $q=0$ of the Hecke algebra
$\mathcal{H}_n(q)$ of the symmetric group (or more generally a Coxeter
group~\cite{Fayers}). Its importance comes, among other things, from its
action by divided difference operators on polynomials leading to the Demazure
character formula. Starting from the work of Norton and
Carter~\cite{Norton,Carter}, it has received attention from community ranging
from combinatorics, algebraic geometry, representation theory and semi-group
theory~\cite{KT}. The goal of this abstract is to define and study the $q=0$
degeneracy of $\mathcal{I}_n(q)$.

This abstract is structured as follows: after some background
(\cref{sec-back}), we first define the $0$-rook monoid $R_n^0$ by a
presentation (\cref{secdef}) and describe some left and right
faithful actions on so-called rook vectors and polynomials
(\cref{secact} and \cref{reduced}). Using these
presentations, we prove that $R^0_n$ is $\JJ$-trivial
(\cref{j-trivial}). In \cref{reptheo}, we investigate the
representation theory of $R_n^0$ including simple and projective modules. We
show (\cref{projH}) that $R_n^0$ is projective over $H_n^0$ and give an
explicit rule for the decomposition numbers (\cref{decnumber}). In
\cref{further}, we discuss some work in progress about the branching
graphs and tower of monoids.

\section{Background}
\label{sec-back}
\subsection{Rook Matrices and rook vectors}

\begin{definition}
A rook matrix is a $n\times n$ matrix with entries
$\lbrace 0,1\rbrace$ and at most one nonzero entry in each row and column.
\end{definition}
We encode it by its \emph{rook vector} of size $n$ whose $i$-th coordinate
is $0$ if there is no $1$ in the $i$-th column of $r$, and the
index of the row with the $1$ in the $i$-th column otherwise.

\begin{example}
The rook matrices $\begin{psmallmatrix}
0 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0\end{psmallmatrix}$ and 
$\begin{psmallmatrix}
0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0\end{psmallmatrix}$
will be denoted by $04231$ and $03041$.
\end{example}
Any permutation matrix is a rook matrix, as any permutation is a rook
vector. The product of two rook matrices is again a rook matrix, so that they
form a finite submonoid of the monoid of matrices. We denote by $\Id_n$ the
identity rook matrix (or its rook vector).

\subsection{Representation theory of $\JJ$-trivial monoid}\label{secJtrivial}
In 1951, Green introduced several preorders on monoids (see for example:
\cite[Chapter V]{Pin}) related to inclusion of ideals. In the following, we
write $\RR$ for right ideal, $\LL$ for left and $\JJ$ for bi-sided. Let
$\KK\in\lbrace\RR,\LL,\JJ\rbrace$ and $\tMonoid$ be a monoid. For $x,y\in
\tMonoid$, we write $x \leq_\KK y$ when the $\KK$-ideal generated by $x$ is
contained in the $\KK$-ideal generated by $y$. For example, if $\KK=\LL$, this
means that $x \leq_\LL y$ if $\tMonoid x\subset \tMonoid y$ or equivalently if
$x=uy$ for some $u\in \tMonoid$. These relations are clearly preorders and
naturally give rise to equivalence relations. For example $x \, \LL \, y$ if
and only if $\tMonoid x = \tMonoid y$. A monoid $\tMonoid$ is called
$\KK$-trivial if all $\KK$-classes are of cardinality one, that is if the
preorders are actual orders. For finite monoid, $\RR, \LL$ and $\JJ$ are
related as follows:
\begin{lem}[\cite{Pin} V. Theorem 1.9]
  A \emph{finite} monoid is $\JJ$-trivial when it is both
  $\RR$ and $\LL$-trivial.
\end{lem}
The representation theory of $\JJ$-trivial monoids has been well
studied by Denton, Hivert, Schilling and Thi\'ery~\cite{DHST}. It turns out
that it is combinatorial: more precisely, one can compute the simple,
projective modules, the Cartan matrix and even the quiver by computing only in
the monoid, without requiring linear combinations. We only summarize very
shortly the result here. We denote by $\idempMon$ the set of idempotents
(elements such that $e^2=e$) of $\tMonoid$.
\begin{theorem}[\cite{DHST}]\label{proposition.simple}
  Let $\tMonoid$ be a $\JJ$-trivial monoid. There are as many as simple
  modules $S_e$ as idempotents $e\in\idempMon$, all of dimension $1$. Their
  structure is as follows: $S_e$ is spanned by some $\epsilon_e$ with the
  action of any $m\in\tMonoid$ given by $m\cdot\epsilon_e=\epsilon_e$ if
  $me=e$, and $0$ otherwise.
\end{theorem}
To describe the projective module, define
\begin{equation}
  \label{eq.rfix}
  \rfix{x} := \min \{e\in \idempMon \suchthat ex=x\},
\end{equation}
the $\min$ being taken for the $\JJ$-order.
\begin{theorem}[\cite{DHST}]
  \label{theorem.projective_modules}
  For any idempotent $e$ denote by $L(e) := Me$, and we set
  \begin{equation}
    L_=(e) := \{x\in Me\suchthat \rfix{x} = e\}
    \quad\text{and}\quad
    L_<(e) := \{x\in Me\suchthat \rfix{x} <_\LL e\} \, .
  \end{equation}
  Then, the projective module $P_e$ associated to $S_e$ is isomorphic to $\K
  L(e)/\K L_<(e)$. In particular, taking as basis the image of $L_=(e)$ in the
  quotient, the action of $m\in\tMonoid$ on $x\in L_=(e)$ is given by: $m\cdot
  x = mx$ if $\rfix{mx} = e$ and $0$ otherwise.
\end{theorem}

\subsection{The $0$-Hecke algebra as the algebra of a $\JJ$-trivial monoid}

By putting $q=0$ in Relation~(1) defining the Hecke algebra, one gets the
quadratic equation $T_i^2 = -T_i$, the braid relations being
unchanged. Further putting $\pi_i:=T_i+1$, the algebra $H_n(0)$ becomes the
algebra of a monoid $H_n^0$ generated by the $(\pi_i)_{i<n}$ with the relation
$\pi_i^2=\pi_i$ and the braid relations. It turns out that $H_n^0$ is
$\JJ$-trivial and that the representation theory of $H_n(0)$ worked out by
Norton and Carter~\cite{Norton,Carter} can be obtained from the general
representation theory of $\JJ$-trivial monoids~\cite{DHST}. Note that, to get
a monoid for $H_n(0)$, a common choice is to put $\pi_i:=-T_i$. However,
this choice does not extend to the rook case.

The key to the representation theory of $H_n^0$ is the following:
\begin{lem}
  Let $x\in H_n^0$. Then, the idempotent $\rfix{x}$ is the maximal element of
  the parabolic subgroup generated by the $\pi_i$'s where $i$ is a right
  descent of $x$, that is $x\pi_i = x$.
\end{lem}
We therefore recover the fact that the projective modules of $H_n^0$ have
their bases indexed by permutations with a given descent set.

\begin{note}
  The reader has to be careful that we are working with the $\pi_i$ basis
  whereas in the literature it is customary to work with the $T_i$ basis. As a
  consequence the eigenvalues $0$ and $-1$ with $T_i$ becomes respectively $1$
  and $0$. The usual simple and projective modules for $H_n(0)$ associated
  with the set $I \subset \llbracket 1, n-1\rrbracket$ are associated with
  $\llbracket 1, n-1 \rrbracket \setminus I$ in our conventions.
\end{note}

\section{Definitions and elementary properties}

We now define the $0$-rook monoid $R_0^n$ by extending the definition of
$H_0^n$.
\subsection{Relations}\label{secdef}

In the relations defining $\mathcal{I}_n(q)$ let $q = 0$ and let $\pi_i = T_i+1$. We get
the quadratic equations $\pi_i^2 = \pi_i$, the braid relations for
$\pi_i$ where $1\leq i\leq n-1$ together with
$$\begin{array}{lll}
(4) & P_i^2 = P_i, &  1\leq i \leq n,\\
(5) & P_i P_j = P_j P_i, & 1\leq i,j \leq n,\\
(6) & P_i \pi_j = \pi_j P_i, & 1\leq i<j \leq n, \\
(7) & P_i \pi_j = \pi_j P_i = P_i, & 1\leq j<i \leq n,\\
(8) & P_{i+1} = P_i \pi_i P_i, & 1\leq i < n.
\end{array}$$
Let $R_n^0$ be the monoid generated by the generators $\pi_1,\dots \pi_{n-1},
P_1,\dots P_n$ and these relations. The latter clearly show that it is
generated only by $P_1,\pi_1,\dots \pi_{n-1}$, and that the Relation $(8)$ is
rather a definition.
Furthermore, $P_n$ is the \emph{zero} of $R_n^0$, that is for any $x\in R_n^0$, one
has $xP_n=P_nx=P_n$.

By induction one can show that putting $\pi_0 = P_1$, the following is an
alternative presentation of $R_n^0$:
$$\begin{array}{lll}
(1) & \pi_i^2 = \pi_i, & 0\leq i \leq n-1, \\
(2) & \pi_i\pi_{i+1}\pi_i = \pi_{i+1}\pi_i\pi_{i+1} & 1\leq i \leq n-2, \\
(3) & \pi_1\pi_0\pi_1\pi_0=\pi_0\pi_1\pi_0=\pi_0\pi_1\pi_0\pi_1 & \\
(4) & \pi_i\pi_j = \pi_j\pi_i & \text{if } \vert i-j\vert \geq 2.
\end{array}$$
This shows that $R_n^0$ is a quotient of the Hecke-monoid at $q=0$ of type
$B$, and that the Hecke-monoid $H_n(q)$ at $q=0$ of type $A$ is a submonoid of it. 

\subsection{Acting on vectors and polynomials}
\label{secact}
Let $r = r_1\dots r_n \in R_n$. The classical right action of $H_n^0$ on
vectors can be extended to $R_n^0$ on rook vectors as follows:
$$ \begin{array}{ll}
(r_1 \dots r_n)\cdot \pi_i =
\begin{cases}
r_1 \dots r_{i-1} r_{i+1} r_i r_{i+2} \dots r_n & \text{if $r_i<r_{i+1}$,} \\
r_1 \dots r_n & \text{otherwise,}
\end{cases}
& \text{ for } 1\leq i \leq n-1.\\
(r_1\dots r_n)\cdot \pi_0 = \ \ 0r_2\dots r_n. & 
\end{array} $$
\begin{lem}
The previous definition is a right monoid action of $R_n^0$ on $R_n$ called
the \emph{right natural action}.
Under this action, $P_j$ acts by killing the first $j$ entries: $(r_1\dots
r_n)\cdot P_j = 0\dots 0r_{j+1}\dots r_n\,$.
\end{lem}

Similarly, we now describe a left action on rook vectors: let $r = r_1\dots
r_n \in R_n$. For $0\leq j \leq n$, we write $j \in r$ if $j \in \lbrace
r_1,\dots, r_n\rbrace$.  The left action of $\pi_i \in R_n^0$ on $r$ can be
described the following way:
\begin{itemize}
\item $\pi_0$ replaces $1$ by $0$ in $r$ if $1\in r$, and fixes $r$ otherwise.

\item For $i>0$, the action of $\pi_i$ on $r$ is
\begin{itemize}
\item if $i, i+1\in r$, call $k$ and $l$ their respective positions. Then
  $\pi_i$ fixes $r$ if $l<k$, otherwise it exchanges $i$ and~$i+1$.
\item if $i \not \in r$ and $i+1\in r$, then $\pi_i$ replaces $i+1$ by $i$.
\item if $i+1 \not \in r$ then $\pi_i$ fixes $r$.
\end{itemize}
\end{itemize}
\begin{lem}
  The previous definition is a left monoid action of $R_n^0$ on $R_n$ called
  the \emph{left natural action}.  Under this action, $P_j$ acts by replacing
  the entries smaller than $j$ by $0$.
\end{lem}

\begin{example}
$\pi_0 \cdot 0342= 0342, \quad \pi_1 \cdot 0342 = 0341, \quad \pi_2 \cdot 0342 = 0342, \quad {\pi_3 \cdot 0342 = 0432}$, \quad ${\pi_0 \cdot 132 = 032}.$
\end{example}
This sheds some light on the link with the type $B$: it is well known that type
$B$ can be realized using signed permutations. The quotient giving the $0$-rook monoid can be
realized by replacing the negative numbers by zeros.

One can also extend the action of $H_n^0$ by isobaric divided differences on
polynomials: the monoid $R_n^0$ acts also on the polynomials in $n$
indeterminates over any ring $k$, $k[X_1, \dots, X_n]$ in the following
way. Let $f \in k[X_1,\dots, X_n]$. Define
\begin{equation}
  f \cdot \pi_0 := f_{\vert X_1 = 0} = f(0, X_2, \dots X_n),
  \qquad\text{and}\qquad
  f \cdot \pi_i := \frac{X_i f - (X_i f) \cdot s_i}{X_i-X_{i+1}}\,.
\end{equation}
Again, $f\cdot P_j = f(0, \dots0, X_j, \dots X_n)$.  It is actually possible
to get an action of the full generic $q$-rook algebra by letting
$f\cdot T_i := q (f\cdot s_i) + (1 - q)(f \cdot (\pi_i - 1))\,.$
Since this action is faithful, this leads to very natural definitions of
the rook-monoids and algebras.

\subsection{Properties of the monoid}

In this subsection, we show that the previous actions are faithful, that is
the given presentation is equivalent to the definition by operators. We work
with the right action proceeding by induction on $n$, using the chain of
inclusions $R_1^0\subset R_2^0\subset \dots \subset R_n^0$. We start by
defining a rook analog of the (inverse) Lehmer code of a permutation.
\begin{definition}\label{defcode}
  Let $m$ be the map from the words on $\ZZ$ to $\NN$
  defined recursively as follows: $m(\epsilon) = 0$ where $\epsilon$ denotes
  the empty word. For any word $\underline{w}$ and any letter $d$,
  \begin{equation}
    m(\underline{w} d) :=
      \begin{cases}
        -d  & \text{if $d\leq0$\,;} \\
        m(\underline{w})+1 & \text{if $0<d\leq m(\underline{w})+1$\,;} \\
        m(\underline{w})   & \text{if $d> m(\underline{w})+1$\,.}
      \end{cases}
    \end{equation}
  A \emph{code} of size $n$ is a word on $\ZZ$ defined recursively by: the
  empty word $\epsilon$ is a code, and $\underline{w}d$ is a code if
  $\underline{w}$ is a code and $-m(\underline{w}) \leq d \leq n$. We denote
  by $C_n$ the set of codes of size $n$.
\end{definition}
\begin{example}
  The codes of size $1$, $2$ and $3$ are the following:
    $\{\sf 0, 1\}, \{00, 01, 02, 1\overline1, 10, 11, 12\}$ and
    \begin{gather*}
    \{\sf 000, 001, 002, 003, 01\overline1, 010, 011, 012, 013, 020, 021, 022,
    023,1\overline1\overline1, 1\overline10, 1\overline11, 1\overline12, \\
    1\overline13,
    100, 101, 102, 103, 11\overline2, 11\overline1, 110, 111, 112, 113,
    12\overline2, 12\overline1, 120, 121, 122, 123\}\,.
    \end{gather*}

  $m({\sf 2836427})=7$, $m({\sf 364\overline{4}294\overline{3}52538}) = 6$,
  $m({\sf 021\overline{1}1254}) = 4$ where $\overline{i}$ stands for $-i$.

The words of $C_9$ with prefix ${\sf 021\overline{1}1254}$ are ${\sf 021\overline{1}1254\overline{4}}$ , ${\sf 021\overline{1}1254\overline{3}}$ , $\dots$, ${\sf 021\overline{1}12549}$.
\end{example}

\begin{notation}
For $i, n \in \mathbb{N}$ we put:
$ \col{n}{i} := 
\begin{cases}
  1 & \text{if $i>n$}, \\
  \pi_n\dots \pi_i & \text{if $0\leq i\leq n$},\\
  \pi_n\dots \pi_1\pi_0\pi_1\dots \pi_i & \text{if $i<0$}.
\end{cases}$
\end{notation}


\begin{definition}
  If ${\sf c} = {\sf c_1\dots c_n} \in C_n$, let $\pi_{\sf c} := \col{0}{\sf
    c_1} \cdot \col{1}{\sf c_2}\cdot \dots \cdot \col{n-1}{\sf c_n} \in
  R_n^0$.
\end{definition}

\begin{example}
Let ${\sf c} = {\sf 11\overline{1}20}$. Then 
$$\pi_{\sf c} = \col{0}{1}\cdot \col{1}{1}\cdot \col{2}{-1}\cdot \col{3}{2} \cdot \col{4}{0} = 1\cdot\pi_1 \cdot \pi_2\pi_1 \pi_0 \pi_1 \cdot \pi_3\pi_2 \cdot \pi_4\pi_3\pi_2\pi_1 \pi_0$$
\end{example}
The key fact is that an element of $R_n^0$ is uniquely determined by its (left
or right) action on the rook identity matrix:
\begin{theorem}\label{reduced}
  For all $n\in \NN$, the maps ${\sf c}\in C_n \mapsto\pi_{\sf c} \in R_n^0$ and $r\in R_n^0
  \mapsto \Id_n\cdot r\in R_n$ and $r\in R_n^0\mapsto r \cdot \Id_n\in R_n$ are
  bijections so that, $\vert C_n\vert = \vert R_n^0\vert = \vert R_n\vert$. In
  particular any element of $R_n^0$ can be expressed in a unique way as
  $\pi_{\sf c}$. Moreover these canonical expressions are reduced.

\label{isoregnat}
  The map $r \mapsto r\cdot \Id_n$, when extended by linearity, is an isomorphism
  of $R_n^0$-modules between the left regular module and natural module.
\end{theorem}
For instance the expression $P_n =\pi_0 \pi_1 \pi_0\pi_2\pi_1
\pi_0\pi_3\pi_2\pi_1 \pi_0\dots \pi_{n-1}\pi_{n-2}\dots\pi_1 \pi_0$ is the
reduced canonical expression of $P_n$. 

Note that, under the compose bijection ${\sf c}\mapsto r := \Id_n\cdot
\pi_{\sf c}$, the integer $m(\sf c)+1$ is the position of the first zero in
$r$. And that the conditions of \cref{defcode} amount to saying that if
a word is reduced, it never exchanges two zeros when applied to $(123\dots
n)$.

\subsection{Green relations for the rook monoid}
In this subsection, we show that $R_n^0$ is $\JJ$-trivial. We generalize the
notion of inversions of permutations to rooks $r = r_1\dots r_n \in R_n$ as
$\Inv(r) = \lbrace (i,j) \suchthat i<j \text{ and } r_i>r_j>0\rbrace$. We also
define its support as $\supp(r) := \lbrace i\suchthat r_i \neq 0\rbrace$ and
its content as ${\cont(r):=\{r_i\neq 0\}}$. We order inversions and supports by
inclusion, and contents of the same length by product order that is if
$\cont(r)=\{c_1<\dots<c_l\}$ and $\cont(r')=\{d_1<\dots<d_l\}$ we write
$\cont(r)\leq\cont(r')$ if for all $i\leq l$ one has $c_i\leq d_i$. We then
define a relation $\preccurlyeq$ over $R_n$. If $r$, $r' \in R_n$ then
\begin{equation*}
r \preccurlyeq r' \Longleftrightarrow 
\begin{cases} 
  \supp(r) \subsetneq \supp(r'), \text{ or }\\
  \supp(r) = \supp(r') \text{ and } 
             \cont(r)\leq\cont(r') \text{ and } 
  \Inv(r) \supseteq \Inv(r'). 
\end{cases}
\end{equation*}
It
is easy to see that this is an order on $R_n$, with $\Id_n$ as maximal element and $0_n = 00...0$ as minimal one.
\begin{proposition}
  The left action is regressive: for $f\in R_n^0$ and $r\in R_n$, one has
  $f\cdot r \preccurlyeq r$. As a consequence, $R_n^0$ is 
  $\LL$-trivial.
\end{proposition}
It is well known (see eg:~\cite{DHST}) that any monoid that has a faithful
regressive left action is $\LL$-trivial. This shows that the $\LL$-preorder on
$R_n^0$ is actually an order. It is a rook analog of the weak order for
permutations (also called permutohedron order). It is also a lattice. However,
it is not a lattice quotient of the type $B$ weak order.

Furthermore, the presentation of $R_n^0$ is symmetric: thus this monoid is
isomorphic to its opposite and is thus also $\RR$-trivial. Finally we have
proved the following:
\begin{theorem}\label{j-trivial}
The monoid $R_n^0$ is $\JJ$-trivial.
\end{theorem}

\section{Representation theory}\label{reptheo}
\subsection{Simple modules}
As explained in \cref{secJtrivial} the representation theory of
$R_n^0$ is governed by its idempotents, as any $\JJ$-trivial monoid. The
following theorem, obtained by writing explicitly the canonical expression of the
elements $\pi_J$, describes them:
\begin{theorem}
  The monoid $R_n^0$ has $2^n$ idempotents: the zero (maximal element) of
  every parabolic submonoid. Let $J \subset \lbrace \pi_0,\dots,
  \pi_{n-1}\rbrace$, and $\pi_J$ the zero of the submonoid generated by
  $J$. It is an idempotent, and furthermore $\pi_J\cdot \pi_i = \pi_i\cdot
  \pi_J = \pi_J$ if and only if $\pi_i\in J$.

The monoid $R_n^0$ has $2^n$ simple modules, all one-dimensional, labeled by the parabolic submonoids. More precisely, $(S_{\pi_J})_{J\subset \lbrace \pi_0, \dots, \pi_{n-1}\rbrace}$ is a complete set of pairwise  non-isomorphic representatives of isomorphism classes of simple $R_n^0$-modules, where $S_{\pi_J}$ is defined in \cref{proposition.simple}.
\end{theorem}


\subsection{Projective modules}
\begin{definition}
  For $\pi\in R_n^0$, we define its left $R$-descent set (respectively its right $R$-descent set) by ${D_L(\pi) = \lbrace 0\leq i\leq n-1 \, \vert \, \pi_i\pi=\pi\rbrace}$ (respectively ${D_R(\pi) = \lbrace 0\leq i\leq n-1 \, \vert \, \pi\pi_i=\pi\rbrace}$).\\
  A set of all elements of $R_n^0$ having the same descent sets is called a
  \emph{$R$-descent class}.
\end{definition}

Unless explicitly stated, all $R$-descents are on the right. There is only a finite number of different $R$-descent sets possible for $\pi
\in R_n^0$ : we call them \emph{$R$-descent type}. We say that a $R$-descent
type is of type $0$ if it has $0$ in it, $1$ otherwise. Similarly to $H_n^0$,
we represent the $R$-descent type by ribbons with either the first column
filled with $0$ if it is a $0$-type, or empty otherwise. We say that a
descent class $D$ is finer than $D'$ if $D \supset D'$. 
\begin{example}
Here is the list of the $R$-descent types for $R_4^0$.
\[\includegraphics[scale=0.7]{Proj/proj_taille_4.pdf}\]
\end{example}

As an application of \cref{theorem.projective_modules} we get :
\begin{theorem}
  The projective indecomposable $R_n^0$-modules are indexed by the $R$-descent
  type $D$, and $P_D$ is spanned by the rooks belonging to the descent class
  $D$ and is isomorphic to the quotient of the associated $R$-descent class by
  the finer $R$-descent classes.
\end{theorem}
See the picture at the left of \cref{fig:proj} for an example of
a projective indecomposable $R_n^0$-module.

\subsection{Restriction to $H_n^0$}
We now investigate the relation between $H_n^0$ and $R_n^0$. The restriction
of simple modules from $R_n^0$ to $H_n^0$ and the induction of simple and projective
modules from $H_n^0$ to $R_n^0$ are described by simple natural rules, which we
don't describe here for space. More interesting are the restriction of
projective modules from $R_n^0$ to $H_n^0$. Indeed, we show that they are
projective on $H_n^0$ and give a precise combinatorial rule.
\begin{definition}\label{fI}
  Let $I\subset\{1,\dots,n\}$ of cardinality $i$. Let $\sigma =i_1\dots i_n
\in \mathfrak{S}_n$. We define $\varphi_I(\sigma)$ to be the rook obtained by
removing the first $i$ entries of $\sigma$ and inserting zeros in positions
indexed by the elements of $I$. We call $\psi : R_n \rightarrow
\mathfrak{S}_n$ which takes a rook, put all zeros at the beginning of the word
and replace them by the missing letters in decreasing order. Then
$\psi \circ \varphi_I = id_{\mathfrak{S}_n}$.
\end{definition}
\begin{example}
For instance $\varphi_{\lbrace 1,3\rbrace}(14235) = 02035$ and $\psi(02410) = 53241$. 
\end{example}

$H_n^0$ is a submonoid of $R_n^0$, thus it acts by left multiplication on
$R_n^0$. It therefore makes sense to consider $R_n^0$ as a $H_n^0$-module:
\begin{theorem}\label{projH}
  $R_n^0$ is projective on $H_n^0$. As a consequence, any $R_n^0$-projective
  module remains projective when restricted to $H_n^0$.
\end{theorem}
\begin{proof}
The proof widely uses the isomorphism between the regular $R_n^0$-module and
  the natural one (\cref{isoregnat}). Since applying $H_n^0$ does not
  create any zeros, there is a filtration of $R_n^0$ in $H_n^0$-modules depending
  on the number of zeros of the elements. By projectivity, it is enough to
  prove that each layer of this filtration is projective.
Each layer of this filtration is a direct sum of modules depending on the
  position of these zeros since the zeros are not moved by the action of
  $H_n^0$.

  For such a summand where zeros are in positions $i\in I$, the map $\psi$ of
\cref{fI} is an injective $H_n^0$-module morphism. Its
  image is the set of permutations which start with $|I|$ descents which is a
  well known projective $H_n^0$-module. 
\end{proof}

We now describe the restriction functor. We will use the product rule of
ribbons (the multiplication rule of ribbon Schur functions in noncommutative
symmetric functions~\cite{KT}). The product of the two ribbons $R$ and $S$ is
the sum of the two ribbons obtained by gluing the topmost leftmost box of $S$
either on the right or below the bottommost rightmost box of $R$.

\begin{definition}
Let $D$ be a type of $R$-descent. Thus $D$ is a set of boxes. A zero-filling of $D$ is a ribbon of shape $D$ with boxes either empty, either with $0$ inside according to the following rules: 
\begin{itemize}
\item In the first column, either every box contains $0$ if $D$ is of type $0$, or none otherwise.
\item Outside of the first column, if a box contains $0$ then there is no box on its left, and all the boxes below also contain zeros. 
\end{itemize}
To each of these fillings we associate the product of a column of size the total number of zeros, times the ribbons obtained from $D$ in which each box with a zero on the filling has been removed, in the same order of appearance. 
\end{definition}

\begin{example}
The following picture shows a $R$-descent type, and two examples of a zero-filling
with the associate respective product (the colors are just to show what happens of each box):
\[
\raisebox{20pt}{\scalebox{0.5}{$\gyoung(;0,;0;;,::;,::;;,:::;,:::;;,::::;;;)$}}
\qquad\qquad
\left(\raisebox{20pt}{\scalebox{0.5}{$\gyoung(!\lime;0,;0!\ylw;;,::;!\lime,::;0!\blu;!\lime,:::;0,:::;0!\red;,::::;;;)$}}, 
\qquad
\raisebox{25pt}{\scalebox{0.4}{$\gyoung(!\lime;,;,;,;,;,!\ylw:;;,::;,!\blu:::;,!\red::::;,::::;;;)$}}\right)
\qquad \qquad
\left(\raisebox{20pt}{\scalebox{0.5}{$\gyoung(!\lime;0,;0!\ylw;;,::;!\lime,::;0!\blu;,:::;,:::;;,!\lime::::;0!\red;;)$}}, 
\qquad
\raisebox{25pt}{\scalebox{0.4}{$\gyoung(!\lime;,;,;,;,!\ylw:;;,::;,!\blu:::;,:::;,:::;;,!\red:::::;;)$}}\right)
\]
\end{example}


\begin{theorem}\label{decnumber}
The indecomposable projective $R_n^0$-module of type $D$ splits as a $H_n^0$-module as the direct sum of all the indecomposable projective $H_n^0$-module whose descent class are obtained in a product coming from a zero-filling of $D$, with multiplicity.
\end{theorem}


\begin{example}\label{excalc} This is an example of decomposition of a indecomposable projective $R_n^0$-module into indecomposable projective $H_n^0$-modules. The colors indicate the different products of zero-filling. See \cref{fig:proj}.
\[\begin{aligned}
\raisebox{5pt}{\scalebox{0.6}{\gyoung(;0;,:;;)}} & = \raisebox{10pt}{\scalebox{0.6}{\gyoung(!\ylw;,:;,:;;)}}+\raisebox{15pt}{\scalebox{0.6}{\gyoung(!\blu;,;,:;,::;)}}
= \raisebox{10pt}{\scalebox{0.6}{\gyoung(!\ylw;,;,;;)}}+\raisebox{5pt}{\scalebox{0.6}{\gyoung(!\ylw;;,:;;)}}+\raisebox{5pt}{\scalebox{0.6}{\gyoung(!\blu;,;;;)}}+\raisebox{10pt}{\scalebox{0.6}{\gyoung(!\blu;,;;,:;)}}+ \raisebox{10pt}{\scalebox{0.6}{\gyoung(!\blu;,;,;;)}}+ \raisebox{15pt}{\scalebox{0.6}{\gyoung(!\blu;,;,;,;)}}
= \raisebox{5pt}{\scalebox{0.6}{\gyoung(;;,:;;)}}+\raisebox{5pt}{\scalebox{0.6}{\gyoung(;,;;;)}}+\raisebox{10pt}{\scalebox{0.6}{\gyoung(;,;;,:;)}}+ 2\, \raisebox{10pt}{\scalebox{0.6}{\gyoung(;,;,;;)}}+ \raisebox{15pt}{\scalebox{0.6}{\gyoung(;,;,;,;)}}.
\end{aligned}\]
\end{example}
\begin{figure}[ht]
\centering
\includegraphics[scale = 0.58]{Proj/Proj22-0-hand}
\quad
\includegraphics[scale = 0.58]{Proj/Proj22-0-restr}
\caption{The decomposition of the $R_4^0$ projective module of type $\lbrace 0, 2\rbrace$ into $H_4^0$ projective modules.}
\label{fig:proj}
\end{figure}
We have shown a way to decompose a projective $R_n^0$-module to projective $H_n^0$-modules. 
The following results tells us that we more precisely have a
decomposition functor.
\begin{theorem}
Let $P_R$ be an indecomposable projective module of $R_n^0$. Write
$P_R=\bigoplus P_H$ its decomposition into indecomposable projective
$H_n^0$-modules. Then the isomorphism of $H_n^0$-module $\tilde{\varphi} :
\bigoplus P_H \rightarrow P_R$ is triangular:
$\tilde{\varphi}(e)=\varphi_{I}(e)+\sum_{e'<e}e',$
with $\varphi_I$ defined in \cref{fI} and $I$ the zero-set linked to $P_H$. 

\end{theorem}
\begin{example}
We know from the \cref{excalc} that there is a $\raisebox{10pt}{\scalebox{0.6}{\gyoung(;,;,;;)}}$ module inside the \cref{fig:proj}, coming from the zero-filling $\raisebox{8pt}{\scalebox{0.6}{\gyoung(0;,:;0;)}}$. This $H_n^0$-module is well-known to have the elements $3214$, $4213$ and $4312$. So ours must contains $\pi_{\lbrace 0,2\rbrace}(3214) = 0104$, $\pi_{\lbrace 0,2\rbrace}(4213) = 0103$ and ${\pi_{\lbrace 0,2\rbrace}(4312) = 0102}$. See \cref{fig:proj}.
\end{example}


\section{Perspectives and towers of monoids}\label{further}
We have the following chain of submonoids: $R_1^0\subset R_2^0 \subset R_3^0
\subset \dots \subset R_n^0 \subset \dots$ We can try to analyse the
properties of this chain in term of tower of monoids~\cite{BL}.

The first thing we need to do so is a way to embed $R_n^0 \times R_m^0$ into
$R_{n+m}^0$. We looked at the following embedding which seems more natural
regarding the action on rook vectors and polynomials:
\[\begin{array}{ccccc}
R_n^0 & \times & R_m^0 & \longrightarrow & R_{n+m}^0 \\
P_i, \pi_j  &  & & \longmapsto & P_i, \pi_j \\
& & P_i, \pi_j & \longmapsto & P_{n+i}, \pi_{n+j}\,.
\end{array}\]
These embeddings are compatible with the usual ones used for $H_n^0$. Note
that they are not injective. Nevertheless they seem to have some nice
properties. For example we give here the rule for restriction of simple
modules:
\begin{theorem}
Let $J$ be a subset of $0, \dots, n+m$ and $S_J$ the simple $R_{n+m}^0$-module associated to this parabolic subgroup. Then there are two possibilities for the restriction:
$$ \res_{R_n^0 \times R_m^0}^{R_{n+m}^0} S_J = \begin{cases} 
S_{J\cap [0, \dots, n-1]} \otimes S_{\lbrace 0 \rbrace \cup (J \cap [n+1,\dots n-1])-n} & \mbox{if } [0, \dots, n] \subset J, \\
S_{J\cap [0, \dots, n-1]} \otimes S_{(J \cap [n+1,\dots n-1])-n} & \mbox{otherwise.}
\end{cases}$$
\end{theorem}
It is also possible to compute the induction using Virmaux
result~\cite{Virmaux}.

For projective modules, the situation is not so nice: In general, $R_n^0$ is not
projective over $R_{n-1}^0$ and $R_{n+m}^0$ is not projective over $R_n^0
\otimes R_m^0$. However, $R_{n+m}^0$is projective over $R_n^0 \otimes
H_m^0$. This gives us a structure of noncommutative symmetric function module
and co-module on the sum of the Grothendieck group of the category of
projective modules $\bigoplus_n K_0(R_n)$, similar to
the case of $H_n^0(B)$. \cite{Huang} \medskip

It is worth noticing that the embedding we choose is not the only one. There
are other choices of what happens to $\pi_0$ of the right-side. We
choose to send it to $P_{n+1}$, but sending it to $1$, $\pi_0$ or to $0 =
P_{n+m}$ also gives other embeddings. All of these embeddings are
non-injective, but it seems that we could also use some combinations of
these choices. We are currently searching for an embedding for which the
projectivity property holds.

\section*{Acknowledgments}

We would like to thanks Jean-Yves Thibon for
suggesting the problem and Vincent Pilaud and Nicolas Thi\'ery for helpful
discussions.

\printbibliography


\end{document}
